package com.rui.shangXueTang.kruskal;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @author : [锐神NO.3]
 * @version : [v1.0]
 * @className : Greedy
 * @createTime : [2022/2/19 19:33]
 * @description : [描述该类的功能]
 */

public class Greedy {

    public static void main(String[] args) {
        //创建一个集合，存储城市
        ArrayList<String> areaList = new ArrayList<>();
        areaList.add("北京");
        areaList.add("上海");
        areaList.add("天津");
        areaList.add("广州");
        areaList.add("深圳");
        areaList.add("成都");
        areaList.add("杭州");
        areaList.add("大连");

        HashSet<String> area1 = new HashSet<>();
        area1.add("北京");
        area1.add("上海");
        area1.add("天津");

        HashSet<String> area2 = new HashSet<>();
        area2.add("广州");
        area2.add("北京");
        area2.add("深圳");

        HashSet<String> area3 = new HashSet<>();
        area3.add("成都");
        area3.add("上海");
        area3.add("杭州");

        HashSet<String> area4 = new HashSet<>();
        area4.add("上海");
        area4.add("天津");

        HashSet<String> area5 = new HashSet<>();
        area5.add("杭州");
        area5.add("大连");

        //电台所覆盖城市的范围
        HashMap<String, HashSet<String>> broadasts = new HashMap<>();
        broadasts.put("K1", area1);
        broadasts.put("K2", area2);
        broadasts.put("K3", area3);
        broadasts.put("K4", area4);
        broadasts.put("K5", area5);

        //用户存储符合要求的电台
        ArrayList<String> keyList = new ArrayList<>();

        String key = null;

        HashSet<String> temp = new HashSet<>();

        while(!areaList.isEmpty()){
            for(String broadcastKey : broadasts.keySet()){
                temp.clear();
                temp.addAll(broadasts.get(broadcastKey));
                temp.retainAll(areaList);
                if(temp.size() > 0 && (key == null || temp.size() > broadasts.get(key).size())){
                    key = broadcastKey;
                }
            }
            if(key != null){
                keyList.add(key);
                areaList.retainAll(broadasts.get(key));
                key = null;
            }
        }
        System.out.println(keyList);
    }
}
